import java.util.ArrayList;
import java.util.List;

/**
 * 深度优先算法
 * 
 * DFS是可用于遍历树或者图的搜索算法，DFS与回溯法类似，一条路径走到底后需要返回上一步，搜索第二条路径。在树的遍历中，首先一直访问到最深的节点，
 * 然后回溯到它的父节点，遍历另一条路径，直到遍历完所有节点。
 * 图也类似，如果某个节点的邻居节点都已遍历，回溯到上一个节点。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，
利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用栈数据结构来辅助实现DFS算法。
根据深度优先搜索的特点，采用递归函数实现比较简单。但也可以不采用递归
 * 
 */
public class 深度搜索demo {
    public static void main(String[] args) {

        DeepGraph deepGraph = new DeepGraph(6);
        //构建 树 图
        deepGraph.addLine(0, 1);
        deepGraph.addLine(0, 2);
        deepGraph.addLine(1, 3);
        deepGraph.addLine(1, 4);
        deepGraph.addLine(2, 4);
        deepGraph.addLine(3, 4);
        deepGraph.addLine(3, 5);
        deepGraph.addLine(4, 5);

        System.out.println("开始执行深度优先搜索");

        deepGraph.dfs(2);
    }

    private static class DeepGraph{
        public int dataCount;
        //模拟图
        List<List<Integer>> dataMap;

        public DeepGraph(int dataCount){

            this.dataCount = dataCount;

            dataMap = new ArrayList<>(dataCount);

            for(int i=0; i<dataCount; i++){

                dataMap.add(new ArrayList<>());
            }


        }

        public void addLine(int start, int end){
            dataMap.get(start).add(end);
        }

        public void dfs(int handle){

            if(handle<0 || handle >= dataCount){

                System.out.println("查找节点输入越界");

                return;
            }
            //记录节点是否被访问
            boolean[] isHandled = new boolean[dataCount];
            dfsHandle(handle, isHandled);

        }

        public void dfsHandle(int handle, boolean[] isHandled){

            isHandled[handle] = true;
            System.out.println(handle+"已处理");
        
            List<Integer> subDataList = dataMap.get(handle);

            if(null ==subDataList || subDataList.isEmpty()){

                System.out.println("没有子节点，搜索结束");

                return;
            }

            for(int data: subDataList){

                if(!isHandled[data]){

                    //递归处理
                    dfsHandle(data, isHandled);
                }
            }
        }

    }
}
